package code1.double_pointer;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 原题链接：https://leetcode.cn/problems/4sum/
 */
public class P18 {

    //四数之和
    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> result=new ArrayList<>();
        Arrays.sort(nums);      //排序
        for(int i=0;i<nums.length;i++){
            if(nums[i]>target && target>=0){
                break;                      //最小的都大于target，说明不存在
            }
            if(i>0 && nums[i]==nums[i-1]){
                continue;                   //对一个元素去重
            }
            for(int j=i+1;j<nums.length;j++){
                if(nums[i]+nums[j]>target && target>=0){
                    break;
                }
                if(j>i+1 && nums[j]==nums[j-1]){
                    continue;               //对第二个元素去重
                }
                int left=j+1;
                int right=nums.length-1;
                while (left<right){
                    long sum=(long) nums[i]+nums[j]+nums[left]+nums[right];    //用例会溢出
                    if(sum>target){
                        right--;
                    }else if(sum<target){
                        left++;
                    }else{
                        List<Integer> list = Arrays.asList(nums[i], nums[j], nums[left], nums[right]);
                        result.add(list);
                        //对第三个元素和第四个元素进行去重
                        while (left<right && nums[left]==nums[left+1]){
                            left++;
                        }
                        while (left<right && nums[right]==nums[right-1]){
                            right--;
                        }
                        left++;
                        right--;        //双指针同时收束
                    }
                }
            }
        }
        return result;
    }
}
